Module# 14: Sorting Techniques Lecture#53: Programs for Sorting Part-I
// Example 53.1: Programming for Insertion
sorting
/* This program sorts
an array of data using Insertion sort technique. */
public class InsertionSort {
public static <T extends Comparable<T>> void insertionSort(T[] arr, int len){
for (int i = 0; i < len; i++){
int j = i;
while (j > 0 && arr[j].compareTo(arr[j-1]) > -1){
T temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j= j-1;
}
}
}
/* The following
method is an auxiliary method to print an array. */
public static <T> void printArray(T[] arr, int len) {
for(int i=0; i<len; i++) {
System.out.print(arr[i] + " ");
}
}
/* The main method to
test the program. */
public static void main(String[] args) {
Integer[] arr = {89,45,95,63,23,41,13,78};
int n = arr.length;
System.out.println("Given
Array:");
printArray(arr, n);
insertionSort(arr, n);
System.out.println("\nAfter
sorting:");
printArray(arr, n);
}
} // End of the program
// Example 53.2:
Programming for Selection sorting
/* This program sorts
an array of data using Selection sort technique. */
public class SelectionSort {
public static <T extends Comparable<T>> void selectionSort(T[] arr, int len){
for(int i=0; i<(len-1); i++){
int minIndex = i;
for(int j=i+1; j<len; j++){
if(arr[minIndex].compareTo((arr[j])) > 0 ){
minIndex = j;
}
}
T temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
/* The following
method is an auxiliary method to print an array. */
public static <T> void printArray(T[] arr, int len) {
for(int i=0; i<len; i++) {
System.out.print(arr[i] + " ");
}
}
/* The main method to test the program. */
public static void main(String[] args) {
Integer[] arr = {89,45,95,23,41,13,63};
int n = arr.length;
System.out.println("Given
Array:");
printArray(arr, n);
selectionSort(arr, n);
System.out.println("\nAfter sorting:");
printArray(arr, n);
}
} // End of the program
// Example 53.3:
Programming for Bubble sorting
/* The following method implements the Bubble
sort algorithm. */
void bubbleSort(){
T temp;
boolean swapped=true;
for(int i=0;i<this.a.length-1 && swapped;i++) {
swapped=false;
for(int j=0;j<this.a.length-i-1;j++) {
if(a[j].compareTo(a[j+1])>0) {
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
swapped=true;
}
}
}
} // End of the Bubble
sort method
} // End of the generic class definition
/* The main method to
test the program. */
public class TestBubbleSort {
public static void main(String[] args){
Integer i[ ] = {59, 44, 79, 74, 88};
// Store the data into generic array
GenericArraySorting<Integer> arrayInt = new GenericArraySorting<Integer>(i);
// Printing the data….
System.out.print("Array Before Sorting : ");
arrayInt.printData();
arrayInt.bubbleSort();
System.out.print("Sorted Array is : ");
arrayInt.printData();
System.out.println();
}
} // End of the program
// Example 53.4:
Programming for Heap sorting (defining generic class)
/* This program
defines a generic class to store a collection. */
public class MinHeap<T extends Comparable<T>> {
private T[] Heap;
private int size;
private int maxsize;
private static final int FRONT = 0;
public MinHeap(T[] arr , T node)
{
this.maxsize = arr.length;
this.size = 0;
Heap = arr;
Heap[0] = node;
}
// Continued to
next...
/* The following are some auxiliary methods.
*/
// Function to return the position of the
parent for the node currently at pos
private int parent(int pos) {
return pos / 2;
}
// Function to return the position of the
left child for the node currently at pos
private int leftChild(int pos) {
return (2 * pos);
}
// Function to return the position of the
right child for the node currently at pos
private int rightChild(int pos) {
return (2 * pos) + 1;
}
/* The following are some auxiliary methods.
*/
// Function that returns true if the passed
node is a leaf node
private boolean isLeaf(int pos) {
if (pos >= (size / 2) && pos <= size) {
return true;
}
return false;
}
// Function to swap two nodes of the heap
private void swap(int fpos, int spos) {
T tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}
/* The following is the method to print a
heap tree. */
public void print() {
for (int i = 1; i <= size / 2; i++) {
System.out.print(" PARENT :
" + Heap[i]
+ " LEFT CHILD :
" + Heap[2 * i]
+ " RIGHT CHILD
:" + Heap[2 * i + 1]);
System.out.println();
}
}
// Function to build
the min heap using the minHeapify
public void minHeap()
{
for (int pos = (size / 2); pos >= 1; pos--) {
minHeapify(pos);
}
}
/* The following is the method to heapify the
tree. */
private void minHeapify(int pos) {
// If the node is a non-leaf node and greater
than any of its child
if (!isLeaf(pos)) {
if (Heap[pos].compareTo(Heap[leftChild(pos)]) > 0
|| Heap[pos].compareTo(Heap[rightChild(pos)]) > 0) {
// Swap with the left child and heapify the
left child
if (Heap[leftChild(pos)].compareTo(Heap[rightChild(pos)]) < 0) {
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}
// Swap with the right child and heapify the
right child
else {
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}
/* The following is the method to insert a
node into the heap tree. */
public void insert(T element) {
if (size >= maxsize) {
return;
}
Heap[++size] = element;
int current = size;
while (Heap[current].compareTo(Heap[parent(current)]) < 0 ){
swap(current, parent(current));
current = parent(current);
}
}
/* Function to remove and return the minimum
element from the heap */
public T remove() {
//System.out.print(size);
T popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}
/* Sorting with
themean heap. */
public T[] sort(T sorted[]){
//System.out.print(maxsize);
int i = 0;
while(size>=0){
T a = remove();
sorted[i] = a;
i++;
}
for(int j = 0;j<i;j++) {
System.out.print(sorted[j] + " ");
}
return sorted;
}
/* The main method to
test the program. */
public static void main(String[] arg) {
System.out.println("The Min Heap is ");
Integer[] a = new Integer[15];
Integer[] x = new Integer[15];
MinHeap minHeap = new MinHeap(a , 5 );
//minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);
minHeap.insert(84);
minHeap.insert(19);
minHeap.insert(6);
minHeap.insert(22);
minHeap.insert(9);
minHeap.minHeap();
minHeap.print();
minHeap.sort(x);
}
} // End of the program